package com.zzy.sort;

/**
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
 * 示例 1：输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]
 * 示例 2：输入：arr = [0,1,2,1], k = 1 输出：[0]
 */
public class JZ40GetLeastNumbers {
    public static void main(String[] args) {
        int[] nums = new int[]{4, 5, 1, 6, 2, 7, 3, 8};
        int[] res = getLeastNumbers(nums, 4);
        for (int num : res) {
            System.out.print(num + ",");
        }
    }

    private static int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];

        buildMinHeap(arr);
        for (int i = arr.length - 1; i > arr.length - 1 - k; i--) {
            swap(arr, 0, i);
            minHeapify(arr, 0, i);
        }
        for (int i = 0; i < k; i++) {
            res[i] = arr[arr.length - 1 - i];
        }
        return res;
    }

    private static void buildMinHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            minHeapify(arr, i, arr.length);
        }
    }

    private static void minHeapify(int[] arr, int parentIndex, int heapSize) {
        int lChild = 2 * parentIndex + 1;
        int rChild = lChild + 1;
        int minIndex = parentIndex;
        if (lChild < heapSize && arr[lChild] < arr[minIndex]) {
            minIndex = lChild;
        }
        if (rChild < heapSize && arr[rChild] < arr[minIndex]) {
            minIndex = rChild;
        }
        if (minIndex != parentIndex) {
            swap(arr, parentIndex, minIndex);
            minHeapify(arr, minIndex, heapSize);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
